package com.hy.greedy;

public class JumpGame {


    /**
     * 55. 跳跃游戏
     * 力扣题目链接
     *
     * 给定一个非负整数数组，你最初位于数组的第一个位置。
     *
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     *
     * 判断你是否能够到达最后一个位置。
     *
     * 示例 1:
     *
     * 输入: [2,3,1,1,4]
     * 输出: true
     * 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
     *  索引 +数组元素值  比大小
     * 思路
     * 刚看到本题一开始可能想：当前位置元素如果是3，我究竟是跳一步呢，还是两步呢，还是三步呢，究竟跳几步才是最优呢？
     *
     * 其实跳几步无所谓，关键在于可跳的覆盖范围！
     *
     * 不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。
     *
     * 这个范围内，别管是怎么跳的，反正一定可以跳过来。
     *
     *     " 那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！"
     *
     *  每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。
     *
     *  " 贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。"
     *
     * 局部最优推出全局最优，找不出反例，试试贪心！
     * @param num
     * @return
     */
    public boolean jumpGame(int [] num){
        if (num.length == 1){
            return true;
        }
        //覆盖范围, 初始覆盖范围应该是0，因为下面的迭代是从下标0开始的
        int cover = 0;
        // 注意这里是小于等于cover  在覆盖范围内更新最大的覆盖范围
        for (int i = 0; i <= cover; i++) {
            cover = Math.max(i+ num[i],cover);
            // 说明可以覆盖到终点了
            if (cover >= num.length -1){
                return true;
            }
        }
        return false;
    }


    public static void main(String[] args) {
        JumpGame jumpGame = new JumpGame();
        int [] num = {2,3,1,1,4};
        int [] num2 = {3,2,1,0,4};
        System.out.println("res: "+ jumpGame.jumpGame(num));
        System.out.println("res2: "+ jumpGame.jumpGame(num2));
    }
}
